// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem239.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\239.滑动窗口最大值.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-27 14:45:43
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-27 16:27:11
 */
/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
class MonotonicQueue 
{
private:
    deque<int> q;
public:
    void push(int n)
    {
        // 加入队列的时，要把队列中小于n的元素放出去。
        while (!q.empty() && q.back() < n)
        {
            /* code */
            q.pop_back();
        }
        q.push_back(n);
        
    }

    int getMax()
    {
        return q.front();
    }

    void pop(int n)
    {
        if(!q.empty() && q.front() == n)
        {
            q.pop_front();
        }
    }
};


class Solution {
private:
    
public:
    //  单调队列解 
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicQueue window;
        vector<int> res;
        for(int i = 0; i < nums.size() ; i++)
        {
            if(i < k - 1)
            {
                window.push(nums[i]);
            }
            else
            {
                window.push(nums[i]);
                res.push_back(window.getMax());
                window.pop(nums[i - k + 1]);
            }
        }

        return res;
    }



    // 优先队列 priority_queue<pair<int, int>> q; 
};
// @lc code=end

